googologywikiaorg-20200223-history
User talk:Wythagoras/Rado's sigma function/Oracle TMs
I wonder how much faster growing \(\Sigma_2(n)\) than \(\Sigma(n)\). For example \(\Sigma_2(100)\) more than \(\Sigma(100)\) in googol times or may be 'graham's number' times?' Konkhra (talk) 10:35, March 20, 2014 (UTC)' :These "times" aren't good when we compare so large numbers. By times we mean multiply, but multiplication is only between \(f_1(n)\) and \(f_2(n)\) in FGH. :When we compare \(\Sigma_2(n)\) and \(\Sigma(n)\), we can compare \(f_{\omega_2^\text{CK}}(n)\) and \(f_{\omega_1^\text{CK}}(n)\). Just think about it. The ordinal \(\omega_2^\text{CK}\) is far larger than \(\omega_1^\text{CK}*2\), \(\omega^{\omega_1^\text{CK}+1}\), \(\varepsilon_{\omega_1^\text{CK}+1}\), \(\Gamma_{\omega_1^\text{CK}+1}\). It is even hard to imagine how to get \(\omega_2^\text{CK}\) from \(\omega_1^\text{CK}\). :However, \(f_{\omega_1^\text{CK}+1}(n)\) is already comparable to \(g(n) = \Sigma^n(n) = \Sigma(\Sigma(\Sigma(\cdots(\Sigma(n))\cdots)))\) (with n nested \(\Sigma\)'s). I can't even explain to you how \(f_{\omega_1^\text{CK}*2}(n)\) compares to \(\Sigma(n)\). Ikosarakt1 (talk ^ ) 16:00, March 20, 2014 (UTC) :I guess that \(\Sigma_2(25) > \Sigma(100)\) and that \(\Sigma_2(100)\) is beyond, say, {L&L,100}100,100 with in the base rule ab replaced with \(\Sigma^b(a)\). :As many have said, it is hard to overestimate \(\Sigma(n)\) with our meager recursive functions. Of course, it's nothing compared to \(f_\lambda(n)\)... FB100Z • talk • 18:26, March 20, 2014 (UTC) ::I'm wondering why the strength of \(\Sigma_2(n)\) is \(\omega_2^\text{CK}\), and not \(\omega_1^\text{CK}*2\). Wythagoras (talk) 18:42, March 20, 2014 (UTC) :::I'm having a little difficulty with this. Let's first examine why \(f_\alpha(n)\) is computable when \(\alpha\) is recursive. If \(\alpha\) is recursive, then we can define a recursive ordinal notation up to \(\alpha\), and therefore define a consistent system of fundamental sequences up to \(\alpha\) recursively. So we have an algorithm for computing \(f_\alpha\), and so \(f_\alpha < \Sigma(n)\). It's less clear why \(f_{\omega_1^\text{CK}}(n)\) should be faster than all computable functions, and don't know if such a thing is even provable. But it seems reasonable that it would be for natural definitions of the fundamental sequences. :::Okay, now let's consider recursivity in 0' (that is, computable when we are allowed the regular Halting Problem as an oracle). If \(\omega_1^\text{CK}\) is recursive in 0', it is easy to see that \(\omega_1^\text{CK}*2\) is recursive in 0', and also any of our recursive ordinal notations where we are allowed to use \(\omega_1^\text{CK}\). By a theorem of Sacks, (see http://en.wikipedia.org/wiki/Admissible_ordinal) "the countable admissible ordinals are exactly those constructed in a manner similar to the Church-Kleene ordinal, but for Turing machines with oracles." So if we constructed Kleene's \(\mathcal{O}\), but used Turing machines with the regular Halting Problem as an oracle rather than regular Turing machines, we would get up to \(\omega_2^\text{CK}\). :::That seems to settle things. Here's the problem, though: \(\omega_1^\text{CK}\) is not even hyperarithmetical! The hyperarithmetical sets are generated by starting from 0 (recursive sets) and iterating the Turing jump up to \(\omega_1^\text{CK}\). (The limit ordinal step is kind of complicated, but let's not worry about that now.) So 0' is certainly included in the hyperarithmetical sets, so \(\omega_1^\text{CK}\) should not be in 0', or \(0^{(\alpha)}\) for any recursive ordinal \(\alpha\). So I'm a bit confused here. Deedlit11 (talk) 12:37, March 21, 2014 (UTC) :::By the way, how do we add links? I tried to add a url code but it got blocked by the spam filter. Deedlit11 (talk) 12:41, March 21, 2014 (UTC) ::::I always thought that relation with order type \(\omega^\text{CK}_1\) is recursively enumerable, thus 0'-computable. Doesn't the following argument work? ::::Imagine machine which tries to compute if ordinal coded by \(n\) in Kleene's \(\mathcal{O}\) is larger than ordinal coded by \(m\). For these two numbers, and all other numbers we are going to get, we assume they indeed code ordinals. We simulate n-th machine on all finite inputs, by dividing tape into infinitely many parts. Eventually, some of these machines might halt. As we assumed \(n\) codes an ordinal, we will get unboundedly (below ordinals below what \(n\) codes) many ordinals. If \(m\) codes ordinal less than \(n\), it is smaller than ordinal coded by some of these outputs. By using well-ordering principle, we will eventually get number \(m\). LittlePeng9 (talk) 14:26, March 21, 2014 (UTC) ::::Try censoring http:// with hxxp://. FB100Z • talk • 20:15, March 22, 2014 (UTC) How do your oracle machines behave in "ask" state when on tape there is non-continuous string of ones? Do you just sum up the number of ones and make query about that machine? LittlePeng9 (talk) 13:49, March 22, 2014 (UTC) :Yes. Is there an other possibility? Wythagoras (talk) 14:29, March 22, 2014 (UTC) ::Interpreting as binary number. LittlePeng9 (talk) 14:36, March 22, 2014 (UTC) ::WaxPlanck (talk) 20:06, December 21, 2017 (UTC) Where is the ask state?